#include<cstdio>
#include "common.h"
#include<cmath>

#include "cuComplex.hpp"
typedef cuComplex<double> K;

#define my_swap(a,b) {__typeof(a) tmp=a;a=b;b=tmp;}

extern "C" {

	__global__
	void reverse_num(unsigned char *A, int n, unsigned char *B, int m) {
		int blockId = blockIdx.x + blockIdx.y * gridDim.x;
		int x = blockId * blockDim.x + threadIdx.x;
		if(x < n/2) my_swap(A[x], A[n-x-1]);
		if(x < m/2) my_swap(B[x], B[m-x-1]);
	}

	__global__
	void reverse(unsigned char *A, char *B, long long n) {
		int blockId = blockIdx.x + blockIdx.y * gridDim.x;
		int x = blockId * blockDim.x + threadIdx.x;
		if(x < n) {
			B[x] = A[n-x-1] + '0';
		}
	}

	__global__
	void init(K *A, unsigned char *Astr, int n, K *B, unsigned char *Bstr, int m, int P) {
		int blockId = blockIdx.x + blockIdx.y * gridDim.x;
		int x = blockId * blockDim.x + threadIdx.x;
		if(x >= P) return;
		{
			int a = 0;
			for(int i=min(DIGS, n-DIGS*x)-1;i>=0;i--)
				a = BASE_BASE*a + (Astr[DIGS*x+i]);
			A[x] = K(a);
		}
		{
			int b = 0;
			for(int i=min(DIGS, m-DIGS*x)-1;i>=0;i--)
				b = BASE_BASE*b + (Bstr[DIGS*x+i]);
			B[x] = K(b);
		}
	}

	__device__ int rev(int x, int P) {
		int y = 0;
		for(int k=1;k<P;k*=2,y*=2) if(k&x) y++;
		y /= 2;
		return y;
	}

	__global__
	void permutate(K *A, int P) {
		int blockId = blockIdx.x + blockIdx.y * gridDim.x;
		int x = blockId * blockDim.x + threadIdx.x;
		if(x >= P) return;
		int y = rev(x, P);
		if(x < y) {
			my_swap(A[x], A[y]);
		}
	}

	__global__
	void multiply(K *A, K *B, int P) {
		int x = (blockIdx.x + blockIdx.y * gridDim.x) * blockDim.x + threadIdx.x;
		if(x >= P) return;
		if(P) A[x] = A[x]*B[x]/P;
	}

	__global__
	void fft(K *arr, int P, int step, int n_step, bool rev) {
		int blockId = blockIdx.x + blockIdx.y * gridDim.x;
		int x = blockId * blockDim.x + threadIdx.x;
		if(x >= P) return;
		if(x & step) return;
		int j = x & (step - 1);
		int i = x - j;
		int A = i+j;
		int B = i+j+step;
		K u = arr[A];
		K v = arr[B];
		K w = K(cos(2*M_PI*(j<<n_step)/P), ((rev)?(1):(-1))*sin(2*M_PI*(j<<n_step)/P));
		K vw = v*w;
		arr[A] = u + vw;
		arr[B] = u - vw;
	}

	__global__
	void result(K *arr, double *res, int P) {
		int blockId = blockIdx.x + blockIdx.y * gridDim.x;
		int x = blockId * blockDim.x + threadIdx.x;
		if(x >= P) return;
		res[x] = arr[x].real() + 0.5;
	}

}

